//q13.cpp
//This program takes an array and a sum and calculate whether the sum is in the array in any way.
//
//Binyamin 11 Jan 2018
//===============================================================================================

#include<iostream>

using namespace std;

//sub_set_sum
//input: array it size and a sum
//output: whether the sum is in the array
bool sub_set_sum(int numbers[], int size, int sum)
{
	int i; // looper
	int swap;
	if(sum < 0)
		return false;
	if(sum == 0)
		return true;
	for(i=0;i<size;i++)
		if(numbers[i] == sum) return true;
	return sub_set_sum(numbers, size-1, sum - numbers[size - 1]) || sub_set_sum(numbers, size-1, sum);
}
//1. generate array
//2. genrate sum
//3 print whether the sum is in the array
int main()
{
	int arr[] = {1, 5, 3, 9, 10};// test array
	int sum = 14;// the sum
	if(sub_set_sum(arr, 5, sum)) cout << "The sum is in the array";
	else cout << "The sum is not in the array";
	cout << endl;
}
//output
//The sum is in the array
